import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 涛
 * Date: 2023-10-21
 * Time: 9:39
 */
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
public class Sort {
    /**
     *  复制带随机指针的链表
     * @param head
     * @return
     */
    public Node copyRandomList(Node head) {
        //创建一个map存放被拷贝和拷贝的node
        Map<Node, Node> map = new HashMap<>();
        Node cur = head;
        //1、遍历一遍链表，把链表的节点放进map中，同时创建一个新的节点
        while(cur != null) {
            Node node = new Node(cur.val);
            map.put(cur,node);
            cur = cur.next;
        }
        //2、修改新节点的指向
        cur = head;
        while(cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        //3、返回新链表的头结点
        return map.get(head);
    }
}
